package baseclass.l_string;

/**
 * 给定一个字符串，要求在拓展原字符串，使得拓展后的字符串存在两个原字符串，
 * 并且要求拓展后的字符串长度最小且不能为原字符串。
 * 如str = abcqabc，拓展后str = abcqabcq，可以拿出两个abcq.
 *  这题的思路就是str的前缀能够被后缀最大利用多少的问题。
 *
 *  思路：求str的next数组，并把next数组多扩展一位，最后扩展出的这一位代表前缀和后缀重复的部分，
 *         也就是可以重复利用的部分，把其他的补在str后面就形成了两个str。
 *
 *     如abc123abc,形成next数组，拓展一位，next数组最后一位的值是3  ，也就是abc和abc共同前后缀。所以把剩下的
 *     中间123贴在str后面即可。
 * @date 2020/3/6 11:21
 */
public class Code04_NextApp {

    public static String getRes(String str){
        if(str == null || str.length() == 0) return str;
        int[] next = getNext(str.toCharArray());
        //譬如str = abcddab,那么得到len位置的 next，ab = ab
        int last = next[next.length-1];
/*        String newStr = str.substring(last);
        return str + newStr;// 如果是abqab  返回abqabqab*/
        return str+ str.substring(last,str.length() - last);//如果是abqab 返回abqab
    }

    private static int[] getNext(char[]arr){
        if(arr == null || arr.length == 0)return null;
        if(arr.length == 1) return new int[]{-1};
        int[]next = new int[arr.length+1];
        next[0] = -1;
        next[1]= 0;
        int cn = 0;
        int i = 2;
        while (i <= arr.length){
            if(arr[i-1] == arr[cn]){
                next[i++] = ++cn;
            }else if(cn == 0){
                next[i++] = 0;
            }else {
                cn = next[cn];
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str = "abc12345abcd";
        System.out.println(str.substring(1, 3));
        System.out.println(getRes(str));

    }
}
